package hash;

/**
 * 有多个课程，多个人，每个人可以报多个课程。
 * 给一些课程号，查询报这些课程的人有多少个
 *
 * @author Liaorun
 */
public class EveryQueryUsers {


    /**
     * @param n 一共多少人
     * @param m 一共有多少课程
     * @param q
     * @param A
     * @return
     */
    public static int[] record2(int n, int m, int q, int[][] A, int[] B) {

        // 需要的bit数量 = Math.ceil(n / 32)
        int needIntsCount = (n + 31) / 32;

        int[][] bitMap = new int[m][needIntsCount];

        for (int i = n; i > 0; i--) {
            for (int kecheng : A[i]) {
                // 记录i号人选了kecheng
                bitMap[kecheng][i / 32] |= 1 << (i % 32);
            }
        }
        int[] ans = new int[q];

        for (int i = q; i > 0; i--) {
            int all = 0;
            for (int j = needIntsCount; j > 0; j--) {
                // status 记录所有课程有那些人选
                int status = 0;

                for (int kecheng : B) {
                    status |= bitMap[kecheng][j];
                }

                // status 二进制有几个1就有几个人选
                all += countOnes(status);
            }

            ans[i] = all;
        }

        return ans;
    }


    /**
     * @param n 一个32整数
     * @return n 中有多少个1
     */
    public static int countOnes(int n) {
        n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);

        return n;
    }
}
